# Full text of "Stopping Sets of Algebraic Geometry Codes"

## See other formats

m < (N Stopping Sets of Algebraic Geometry Codes Jun Zhang, Fang-Wei Fu and Daqing Wan Abstract Stopping sets and stopping set distribution of a linear code play an important role in the performance analysis of iterative decoding for this linear code. Let C be an [n, k] linear code over F^ with parity-check matrix H, where the rows of H may be dependent. Let [n] = {1, 2, • • • ,n} denote the set of column indices of H. A stopping set S of C with parity-check matrix iJ is a subset of [n] such that the restriction of H to S does not contain a row of (<— ^ , weight 1. The stopping set distribution {Ti(iJ)}"^Q enumerates the number of stopping sets with size i of C with CN I parity-check matrix H. Denote H* the parity-check matrix consisting of all the non-zero codewords in the dual Jh ' code C^. In this paper, we study stopping sets and stopping set distributions of some residue algebraic geometry (AG) codes with parity-check matrix H*. First, we give two descriptions of stopping sets of residue AG codes. For the simplest AG codes, i.e., the generalized Reed-Solomon codes, it is easy to determine all the stopping sets. Then we consider AG codes from elliptic curves. We use the group structure of rational points of elliptic curves to present a complete characterization of stopping sets. Then the stopping sets, the stopping set distribution and the stopping distance of the AG code from an elliptic curve are reduced to the search, counting and decision versions of the subset sum problem in the group of rational points of the elliptic curve, respectively. Finally, for some special t/3 ' cases, we determine the stopping set distributions of AG codes from elliptic curves. Index Terms ^ ' Stopping sets, stopping set distribution, stopping distance, algebraic geometry codes, elliptic curves, subset f— ^ . sum problem. ■^ '■ I. Introduction O Let C be an [n, k, d] linear code over F^ with length n, dimension k and minimum distance d. Let H j> be a parity-check matrix of C, where the rows of H may be dependent. Let [n] = {1, 2, ■ ■ ■ , n} denote /\ the set of column indices of H. A stopping set S of C with parity-check matrix iJ is a subset of [n] such H ■ that the restriction of H to S, say H{S), does not contain a row of weight I. The stopping set distribution {Ti{H)}1^Q enumerates the number of stopping sets with size i of C with parity-check matrix H. Note that the empty set is defined as a stopping set and Tq{H) = L A number of researchers have recently studied the stopping sets and stopping set distributions of linear codes, e.g., see [1, 2, 5-18, 20, 21, 24- 26, 28, 32-36]. Stopping sets and stopping set distribution of a linear code are used to determine the performance of this linear code under iterative decoding [5]. The first two authors are supported by the National Key Basic Research Program of China (973 Grant No. 2013CB834204), and the National Natural Science Foundation of China (Nos. 61171082, 10990011 and 60872025). This paper was presented in part at the 9th Annual Conference on Theory and Applications of Models of Computation, Turing Centenary Meeting, Chinese Academy of Sciences, Beijing, China, May 16-21, 2012. Jun Zhang is with the Chem Institute of Mathematics, Nankai University, Tianjin, 300071, P.R. China, e-mail: zhangj un04 @ mail .nankai . edu. en Fang-Wei Fu is with the Chem Institute of Mathematics and LPMC, Nankai University, Tianjin, 300071, P.R. China, e-mail: fwfu@nankai.edu.cn Daqing Wan is with the Department of Mathematics, University of California, Irvine, CA 92697-3875, USA. e-mail: dwan@math.uci.edu cd The stopping distance s{H) of C with the parity-check matrix H is the minimum size of nonempty stopping sets. It plays an important role in the performance analysis of the iterative decoding, just as the role of the minimum Hamming distance dof a code for maximum-likehood or algebraic decoding. Analogously to the redundancy of a linear code, Schwartz and Vardy [28] introduced the stopping redundancy p{C), the minimal number of rows in the parity-check matrix H for the linear code C such that the stopping distance s{H) = d, to characterize the minimal "complexity" of the iterative decoding for the code C. The stopping redundancy of some linear codes such as Reed-MuUer codes, cyclic codes and maximal distance separable (MDS) codes have been studied recently [8, 11-13, 28]. Note that the stopping distance, the stopping sets and stopping set distribution depend on the choice of the parity-check matrix H of C. Recall that H* is the parity-check matrix consisting of all non-zero codewords in the dual code C^. For any parity-check matrix H, it is obvious that Ti{H) ^ Ti{H*) for all i, since iJ is a sub-matrix formed by some rows of H* . Although the iterative decoding with the parity-check matrix H* has the highest decoding complexity, it achieves the best possible performance as it has the smallest stopping set distribution. It is known from [34] and [16] that the iterative decoding with the parity-check matrix H* is an optimal decoding for the binary erasure channel. The stopping set distribution is used to characterize the performance under iterative decoding. So it is important to determine the stopping set distribution of C with the parity-check matrix H* . However, in general, it is difficult to determine the stopping set distribution of C with the parity-check matrix H* . Using finite geometry, Jiang et al. [17] gave characterizations of stopping sets of some Reed-MuUer codes (the Simplex codes, the Hamming cods, the first order Reed-MuUer codes and the extended Hamming codes). And they determined the stopping set distributions of these codes. Since the iterative decoding with parity-check matrix H* has the highest decoding complexity, they [17] considered a parity-check matrix H, a submatrix of H*, such that the stopping set distribution of C with parity-check matrix H is the same as that with H*, but has the smallest number of rows. Such a parity-check matrix H is called optimal in certain sense. In general, it is difficult to obtain an optimal parity-check matrix for a general linear code. In [17], they obtained optimal parity-check matrices for the Simplex codes, the Hamming cods, the first order Reed- MuUer codes and the extended Hamming codes. They also proposed an interesting problem to determine the stopping set distributions of well known linear codes with the parity-check matrix H*. In this paper, we consider AG codes and a specific class of AG codes, i.e., AG codes associated with elliptic curves. From now on, we always choose the parity-check matrix H* for linear codes in this paper It is well- known that Proposition 1 ([28]). Let C be a linear code with minimum distance d{C), and let H* denote the parity- check matrix for C consisting of all the nonzero codewords of the dual code C-^. Then the stopping distance s{H*) = d{C). Note that the generalized Reed-Solomon codes are MDS codes. For the [n, k, d] MDS code C, i.e., d = n — k + 1, its dual code C"*- is still an [n,n — k,k + 1] MDS code. Since any non-zero codeword in C"*- has at most n — k — I zeros and any (n — k) positions form an information set, we have Proposition 2. Let C be an [n,k,n — k + 1] MDS code. Then (i) any subset of [n] with cardinality ^ n — k + 1 is a stopping set; (ii) any non-empty subset of [n] with cardinality ^ n — k is not a stopping set. By Proposition 2, we obtain the stopping set distribution of MDS codes. Corollary 3. Let C be an [n,k,n — k + l] MDS code. Then the stopping set distribution of C is given by [ 1, if^ = ^, Ti{H*) = I 0, ifl^i^n-k, [ (^), ift^n-k + 1. As a generalization of the generalized Reed-Solomon codes, next we study the stopping sets and stopping set distributions of AG codes. Constructions of AG codes. Without more special instructions, we fix some notation valid for the entire paper. • X/¥g is a geometrically irreducible smooth projective curve of genus g over the finite field ¥g with function field ¥g{X). • X{¥q) is the set of all ¥ q-rational points on X. • D = {Pi, P2, ■ ■ ■ , Pn} is a proper subset of X(¥q). • Without any confusion, also write D = Pi + P2 + ■ ■ ■ + Pn- • G is a divisor of degree m (2g — 2 < m < n) with Supp(G') H D = 0. Let y be a divisor on X. Denote by ^(V) the F^-vector space of all rational functions / G ¥q(X) with the principal divisor div(/) ^ —V, together with the zero function. And Denote by n(y) the Fg- vector space of all the Weil differentials cu with divisor div(a;) ^ V, together with the zero differential (cf. [31]). For any Fg -rational point P on X, choose one uniformizer t for P. Then for any differential cu, we can write cu = udt with some u E ¥q(X). Write the P-adic expansion u = Xli^j '^j^* f^^ some io E Z and ai E ¥q, the residue map of cu at the point P is defined to be resp{uj) = resp^tiu) = a_i. One can show that the above definition is well-defined [31, Proposition 4.2.9]. The residue AG code Cn{D, G) is defined to be the image of the following residue map: res: n{G - D) -^ F^ Lu ^ {resp^{u),resp^{u),--- ,resp„{u)) . And its dual code, the functional AG code C^{D, G) is defined to be the image of the following evaluation map: They are linear codes over F^, and have the code parameters [n,n — m + g — l,d ^ m — 2g + 2] and [n, m—g+l, d ^ n—m], respectively. And they can be represented from each other [31, Proposition 8.1.2]. For the simplest AG codes, i.e., the generalized Reed-Solomon codes, we have determined all the stopping sets. Then we consider the AG codes Cq{D,G) from elliptic curves. In this case, using the Riemann-Roch theorem, the stopping sets can be characterized completely as follows. Main Theorem. Let E be an elliptic curve over F^, D = {Pi,P2, ■ ■ ■ ,P„} a subset of E{¥q) such that the zero element O ^ D and let G = mO (0 < m < n). The non-empty stopping sets of the residue code Gq{D,G) are given as follows: (i) Any non-empty subset of [n] with cardinality ^ m — 1 is not a stopping set. (ii) Any subset of [n] with cardinality ^ m + 2 is a stopping set. (iii) AC [n], ^A = m + 1, is a stopping set if and only if for all i E A, the sum jeA\{i} (iv) AC [n], ^A = m, is a stopping set if and only if jeA (v) Denote by S{m) and S{m + 1) the two sets of stopping sets with cardinality m and m + 1 in the cases (iv) and (iii), respectively. Let ^+(m)= U {AU{i}:ie [n]\A} . Then the union in ^^(m) is a disjoint union, and we have S{m + l)r\S+{m) =(lS , and S'(m + 1) = {all subsets of [n] with cardinalitym + 1} \ S^{m) . The proof will be given in Section 3. By this theorem, the stopping set distribution of Cq{D, G) follows immediately. Theorem 4. Notation as above. The stopping set distribution of Cq{D,G) with the parity-check matrix H* is ifi = 0, if 1 ^ i ^ m — 1, if i = m, if i = m + 1, if i ^ m + 2 . 1, 0, Ui)-(n-m)#5(m), Then by Theorem 4, we easily see that the stopping distance of Cn{D, G) is m or m+ 1. But to decide it is equivalent to a decision version of m-subset sum problem [19, 22, 23] in the group E(¥g), which is an NP-hard problem under RP-reduction [3]. Hence to compute the stopping distance of Cq{D, G) is NP-hard under RP-reduction. To compute the stopping set distribution is a counting version of m-subset sum problem in the group E{¥g), so it is also an NP-hard problem. But for a special D C E{¥g) with strong algebraic structure, it is possible to compute the complete stopping set distribution. For instance, if we take D = P\ {O}, where P is a subgroup of E(¥q). In particular, in application we always choose D = E{¥g) \ {0} to get a long linear code which is called standard elliptic code. Denote A^ = \P\ the cardinality of P, exp(P) the exponent of P, P[d] the rf-torsion subgroup of P, and 1 >r^ , . . ™ , , ™ , fN/s - r \m/s\ N{m) s\ exp(P) -1) m+LfJ d\s fi{s/d)i^P[d] , ifi = 0, if 1 ^ i ^ m ~ 1, if i = m, if i = m + 1, if i^ m + 2 . respectively. It is known from [19, 23] that ^S{m) = N{m). Hence, we have Theorem 5. Let D = P\{0}, where P is a subgroup of E{¥q). The stopping set distribution ofGn{P>, G) with the parity-check matrix H* is { ^' 0, T,{H*) = I N{m), This paper is organized as follows. In Section 2, we study stopping sets of an arbitrary AG code and give algebraic and geometric descriptions of stopping sets. In Section 3, we study the stopping sets and stopping set distributions of AG codes Cq{D, G) from elliptic curves. We use the group structure of rational points of elliptic curves to present a complete characterization of stopping sets. It is shown that the stopping sets, the stopping set distribution and the stopping distance of the AG code from an elliptic curve can be reduced to the search, counting and decision versions of the subset sum problem in the group of rational points of the elliptic curve, respectively. We present the counting formula for the stopping set distributions of AG codes from elliptic curves. In particular, for some special cases, we determine explicitly the stopping set distributions of AG codes from elliptic curves. Finally, some conclusions and open problems are given in Section 4. II. Stopping Sets of Algebraic Geometry Codes Let X/Fg be a geometrically irreducible smooth projective curve of genus g over the finite field ¥g with function field ¥g(X), and Cfi{D, G) the residue AG code from X. In this section, we study stopping sets and stopping set distributions of general residue AG codes and give algebraic and geometric descriptions of the stopping sets of Cfi{D, G). Theorem 6. A subset A C [n] is a stopping set of Cn{D, G) if and only if ^{g-J2p,) = [j^{g- J2 p^)- jeA ieA j&A\{i} Proof: By the definition, A C [n] is not a stopping set of Gn{D,G) if and only if there is some f e^{G) such that ev{f)\A = {fim^eA has weight 1. That is, there is some i E A such that f{Pi)^0 and f{P,) = for all J e A\{t} . This is equivalent to saying that j&A\{i} jeA So A is a stopping set if and only if for any i E A, jeA jeA\{i} Since ^{G - Zj^a Pj) ^ ^(^ - EjeA^ Pj) for any t E A, we have -^{G - Y^jeA Pj) = UieA -^(G - Y.jeA\{i} Pj) ^^ ^{G - Y.,eA Pj) = ^{G - EjeAm P,) for any i E A. So the theorem holds. ■ As a simple corollary, we obtain Corollary 7. (i) Any subset of [n] with cardinality ^ m + 2 is a stopping set of Gq{D, G). (ii) Any non-empty subset of [n] with cardinality ^ m — 2g + 1 is not a stopping set of Gq{D, G). Proof: (i) For any subset A C [n] with cardinality ^ m+2, divisors C — ^ g^wo Pj and G — ^-^^ Pj are negative. So ^{G-j2Pj) = [j^{G- J2 p^) = w- j€A i€A iGA\{j} It follows from Theorem 6 that A is a stopping set. (ii) For any non-empty subset A C [n] with cardinality ^ m — 2g + l,hy the Riemann-Roch theorem we have dimi-^iG-EjeAPj)) = m-#A-g + l, dim(^(G-E,eA\«^.)) = m-i^A-g + 2. So jdA 3&A\{i} for all i E A.li follows from Theorem 6 that A is not a stopping set. Note that one can also give another proof of (ii) from Proposition 1, since the minimum distance of Cn{D, G) is at least m — 2g + 2. ■ If we represent the generalized Reed-Solomon codes as AG codes from the rational function field, then by Corollary 7, we also obtain Proposition 2 for the generalized Reed-Solomon codes. Using the Riemann-Roch theorem, we give another description of stopping sets of AG codes Cn{D, G). Theorem 8. A subset A C [n] is a stopping set of Gn{D, G) if and only if for any i E A, there exists an effective divisor Ei with Pi ^ Supp(ii^j) such that K-G + J2P3-E^^ jeA where K is a canonical divisor on X and ~ means that two divisors are linearly equivalent, i.e., the difference between the two divisors is a principal divisor Proof: From the proof of Theorem 6, a subset A C [n] is a stopping set if and only if for any i G A, dim^(G - J2 P]) = dim^{G - ^ Pj) . jeA jeA\{i} The Riemann-Roch theorem states that for any divisor V, we have dim^(\/) = deg(\/) - ^ + 1 + dim^{K - V) . So a subset A C [n] is a stopping set if and only if for any i E A, dim^{K -G + J2Pj) = dim^{K -G+ J^ ^j) + ^ • jeA j&A\{i} It is equivalent to that for any i E A, there exists jeA jeA\{i} The last statement is equivalent to that for any i e A, there exists an effective divisor E^ with Pi ^ Supp(-Ei) such that Indeed, E^ = div(/) + K-G + ^jeA Pj- ■ By Theorem 8, we immediately have a sufficient condition for a subset to be a stopping set. Corollary 9. Keep notation as above. Let A be a subset of [n]. If K — G + J2jeA Pj ~ -^ f^^ some effective divisor E whose support has no intersection with {Pi\i E A}, then A is a stopping set. III. Stopping Sets and Stopping set Distributions of AG Codes from Elliptic Curves In the previous section, for the general AG code Cq{D, G), we have seen that there is a gap, deg(G') — 2g + 2 ^ i ^ deg(G') + 1, where in general we have not determined whether a subset with cardinality i is a stopping set or not. In this section, we consider a class of special AG codes, AG codes constructed from elliptic curves. Let X = E he an elliptic curve over the finite field F^ with a rational point O. Endow E(¥q) a group structure with the zero element O. Let D = {Pi, P2, ■ ■ ■ , Pn} be a subset of the set E(¥q) such that O ^ D.let G = mO (0 < m < n). In general, if G is a divisor of degree m on E, then for any rational point Q E E{¥g), as deg{G — [m — l)Q) = 1, by the Riemann-Roch theorem, there exists one and only one rational point P E E(¥g) such that G ~ (m — 1)Q + P. Suppose there exist rational points Q, P such that G ~ (m — 1)Q + P and P,Q i D. Let G' = {m - l)Q + P. Then the codes Gn{D, G) and Gn{D, G') are equivalent [31, Proposition 2.2.14]. And the dual codes G^{D,G) and G^{D,G') are also equivalent. Here two linear codes Gi, G2 C F^ are said to be equivalent if there is a vector a = (ai, ■ ■ ■ , a„) E (F*)" such that G2 = a ■ Gi = {(aici, ■ ■ ■ , anCn) \ (ci, ■ ■ ■ , c„) G Gi} . It is easy to see that two equivalent codes have the same stopping sets and hence the same stopping set distributions. So to study the stopping sets and the stopping set distribution of Gq{D,G), it suffices to determine all the stopping sets and the stopping set distribution of Gq{D , (m — 1)Q + P). In this case, we use Q to define the group E{¥g) with the zero element Q. Then all results in this paper hold similarly for GniD, G) with G ~ (m - 1)Q + P such that P,Q ^ D. Note that g = I for elliptic curves. According to Corollary 7, any subset of [n] with cardinality ^ m + 2 is a stopping set and any non-empty subset of [n] with cardinality ^ m — 1 is not a stopping set. So it is enough to consider the subsets of [n] with cardinality m and m+l. Below we use the group E(¥g) [27, 30] to give a description of these two classes of stopping sets with cardinality m and m + l, respectively. (i) Suppose A C [n] with cardinality m + 1 is not a stopping set. Then there are some i E A and / G ^(G) such that Note that and jeA\{i} jeA deg(G — yj Pj) = m — m = , jeA\{i} div(/)^-G+ Yl P^- jeA\{i} Since both sides have degree zero, so div(/) = -G+ Y. p^= E ^p^-0)- jeA\{i} jeA\{i} In this case, AC [n], ^A = m + 1, is not a stopping set if and only if there exists some i E A such that the sum J^jeAUi} ^i ^'^ ^he group E{¥q) is O. (ii) Suppose A C [n] with cardinality m is a stopping set. By Theorem 6, for any i G A, we have •^{G- Y P,)=^{G-Yp^)- jeA\{i} jeA But deg(G- Y ^,) = 1>2(?-1 = 1, jeA\{i} by the Riemann-Roch theorem, there exists some / G Fg(_E) such that O^fe^G- Y Pj)=nG-YP^)- jeA\{i} jeA So div{f) = G-YP^ = Y.(0-P,). j&A j&A This is equivalent to jeA in the group E(¥g). Conversely, let A C [n] with cardinality m such that XljeA-^i ~ G. Since the zero divisor fi' = is a canonical divisor for elliptic curves, we have K-G + Y^J^^ ■ jeA By Corollary 9, A is a stopping set. From the argument above, we obtain the following partial results of the main theorem in the introduction. 10 Theorem 10. Let E be an elliptic curve over the finite field Fg, D = {Pi,P2,- ■ ■ ,Pn} <3 subset of E{¥q) such that the zero element O ^ D and let G = mO (0 < m < n). The non-empty stopping sets of the residue code Cq{D,G) are given as follows: (i) Any subset of [n] with cardinality ^ m — 1 is not a stopping set. (ii) Any subset of [n] with cardinality ^ m + 2 is a stopping set. (iii) A C [n], ^A = m + 1, is a stopping set if and only if for all i E A, the sum j€A\{i} (iv) AC [n], ^A = m, is a stopping set if and only if j&A Let us give an example to illustrate the theorem. Example 11. Let E be an elliptic curve defined over F5 by the equation y'^ = x^ + X + \ . Then E has 9 rational points: the infinity point O and Pi = (0, 1), P2 = (4, 2), P3 = (2, 1), P4 = (3, 4), P5 = (3, 1), Pe = (2, -1), Py = (4, -2), Pg = (0, -1). Using Group Law Algorithm 2.3 in [30], one can check that -^(Fs) forms a cyclic group with Pj = [i]Pi. Let D = {Pi, P2, ■ ■ ■ , Ps} and G = 30. By Corollary 9 and Theorem 10, all nonempty stopping sets of Cq{D,G) are given as follows: (i) subsets of [n] with cardinality ^ 5; (ii) {1,2,3,7}, {1,2,3,8}, {1,2,4,5}, {1,2, 4,7}, {1,2,4,8}, {1,2,5,7}, {1,2,5,8}, {1,2,7,8}, {1,3,4,6}, {1,3,4,7}, {1,3,4,8}, {1,3,6,7}, {1,3,6,8}, {1,4,5,6}, {1,4,5,7}, {1,4,5,8}, {1,4,6,7}, {1,4,7,8}, {1,5,6,8}, {1,5,7,8}, {1,6,7,8}, {2,3,5,6}, {2,3,5,7}, {2,3,5,8}, {2,3,6,7}, {2,3,6,8}, {2,4,5,6}, {2,4,5,7}, {2,4,5,8}, {2,4,6,7}, {2,4,7,8}, {2,5,6,8}, {2,5,7,8}, {2,6,7,8}, {3,4,5,6}, {3,4,5,7}, {3,4,5,8}, {3,4,6,7}, {3,5,6,8}, {4,5,7,8}; (iii) {1,2,6}, {1,3,5}, {2,3,4}, {3,7,8}, {4,6,8}, {5,6,7}. So the stopping set distribution of Gq{D, G) with the parity-check matrix H* is '1, ifi = 0, 6, if ? = 3, Ti{H*) = \ 40, if i = 4, 0, otherwise. Also, the minimum distance of the code Cq{D, G) is 3 by Proposition 1. Theorem 10 describes all the stopping sets of residue AG codes from elliptic curves. Next, we establish 11 the relationship between the set of stopping sets with cardinality m and the set of stopping sets with cardinality m + 1. Denote by S{m) and S{m + l) the two sets of stopping sets with cardinality m and m + 1 in the cases (iv) and (iii) in Theorem 10, respectively. Let S^{m) be the extended set of S{m) defined as follows S+{m)= [j {AU{i}:ie[n]\A} . AgS{m) Theorem 12. Notation as above. We have S{m + 1) n S+{m) = , and S{m + 1) = {all subsets of [n] with cardinality m + 1}\ S^{m) . Moreover, the union in the definition of S^ {m) is a disjoint union. Hence #^(m+l) = (jJ-#5+(m) = Ui)-(^-m)#5(m). Proof: First, S{m + 1) fl S^{m) = is obvious by parts (iii) and (iv) of Theorem 10. So S{m + 1) C {all subsets of [n] with cardinality m + 1} \ S^{m). On the other hand, for any A ^ S{m + 1) and ^A = m + 1, by Theorem 10 (iii), there is some i E A such that EieA\{i} Pj = O. By Theorem 10 (iv), A\{i} e S{m). So A= {A\{i])yj{i] eS+{m) . Hence S{m + 1) = {all subsets of [n] with cardinality m + 1} \ S^{m) . If there exist A G S{m), A' G S{m), i ^ A and i' ^ A' such that Ayj{i] = A'yj{i'}eS+{m) . Then we have i e A' , i' e A and A \ {%'} = A' \ {i}. Since jeA jeA' we get Pi = Pi'. So A = A\ i = i' . 12 That is, the union in the definition of S^{m) is a disjoint union. And the formula #5(m + l) = Ui)-#5 ^^m) Ui)-(^-^)#^( m] follows immediately. ■ Remark 13. The above theorem shows how we can get S{m + 1) from S{m). Conversely, if we know S{m + 1), then by the above theorem, we can exclude S{m + 1) from the set of all subsets of [n] with m+ 1 elements to get S^{m). For any / G S^{m), we calculate Y^iei ^i- Then by Theorem 10 (iv), there is some index j{I) E I such that i&I By the definitions of S{m) and S^{m), we have S{m) = {I\{j{I)}\IeS+{m)} . In the above example, by Theorem 10 (iv), S'(3) consists of all the subsets of [8] whose sums have 9 as a divisor. Then by Theorem 12, S'(4) follows immediately from S'(3). The following corollary follows immediately from Proposition 1, Theorems 10 and 12. Corollary 14. Notation as above. The minimum distance and the stopping distance of the residue AG code Cq{D,G) is deg(G') or deg(G') + 1. More explicitly, if ij^Sim) > 0, then we have the stopping distance siCniD, G)) = d{Cn{D, G)) = m = deg(G') . If i^S{m) = 0, then we have i^S{m + 1) > and hence s{Cn{D, G)) = d{Cn{D, G)) = m + 1 = deg(G) + 1 . Let Q be an abelian group with zero element O and D a finite subset of Q. For an integer < A; < |D| and an element b E D we denote Ng{k,b,D) = j^{S<ZD\i^S = k and ^x = b} . xes Computing Ng{k,b,D) is called a counting version of the k-subset sum problem (A;-SSP). In general, a counting k-SSF is NP-hard [4]. If there is no confusion, we simply denote N{k,b,D) = Ng{k,b,D) . Remark 15. By the above theorem, for a general subset D C E(¥g), to decide whether ^S{m) > is the decision m-subset sum problem in E(¥g). It is known that the decision m-subset sum problem in E{¥q) in general is NP-hard under RP-reduction [3]. So to compute the stopping distance of Cn{D, G) 13 is NP-hard under RP-reduction. But for a subset D C E(¥g) with special algebraic structure, it is possible to give an explicit formula for ^S{m) = N(m, O, D), and hence explicit formulae for #S'(m+l) and the whole stopping set distribution by Theorem 12. In the following, we consider special subsets D = P \ {0} for some subgroup P of E(¥q). In particular, recall that Cn{D, G) is called the standard elliptic code if D = E(¥g) \ {O}. Proposition 16 ([19, 23]). Let Q be a finite abelian group. For h eQ, we have N{^, b, G \ {0}) = ^ E ^-^^^^ {^u,~\ ■ ^ /^(^/^)#^M • s|cxp(g) V L / J / d| gcd(e(6),s) where N = ^Q, exp(^) is the exponent ofQ, e{h) = maxjrf | d\ exp(^), b G dQ}, /i is the Mobius function and Q[d] is the d-torsion subgroup of Q. Set ^ = P a subgroup of Ei¥q) in Proposition 16. Let A^ = |P| = n + 1 and D = P \ {O}. Then we have Theorem 17. The number of stopping sets of Cn{D,mO) with cardinality m is s|exp(P) V L / J / ^1^ So together with Theorems 10 and 12, we obtain Theorem 5. It is well-known that the group E(¥q) of rational points is isomorphic to E(¥g) ^ Z/miZ © Z/maZ , for some integers mi\m2. Then by Theorems 10, 12 and 17, we can determine the stopping set distribution of the standard residue AG code CQ{D,mO) from any elliptic curve E/¥g provided that we know the group structure of E{¥q). Explicitly, we can compute #5'(3) in Example 11: #^(3) = I E.|9(-1)'^L!J (9/-1) E,|,^(s/rf) \Z/9Z[d]\ = |(© + (D(3-l)-(9-3))=6. So #5(4) = (^) — (8 — 3)#S'(3) = 40. This agrees with the exhausting calculation in Example 11. If we take special subgroups of E(¥g), then we have the following corollary. Corollary 18. Notations as above. (i) If we take P ^ Z/p*Z 14 for some prime integer p and integer t ^ 1, then [logp{m)J In particular, if t = 1, then #^M = ^((''^^) + (-ir(p-i)) Ift = 2, then mm) = \[i^J) + (-i)™(/ -p) + (-ir^^^ -(p- !)(%/ p ■ (ii) //'we tofe P^ 'L/p^'"L®'L/p^^'L for some prime integer p and integers 1 ^ ti ^ t2, then t2 f i+rahi{i,t\} _ j-l+min{i-l,ti}^ '- \ \ in I ' — ■ v I -T I / (iii) If we take for two distinct prime integers pi,P2 and integers ti,t2 ^ 1. then #s{m) = -^ I e^f -^) + (pi - i)(p, - 1) ■ E E(-i)"^^^^>^^VrvrH^'"L'i:;-') +E(-ir^*\'-;i?-')(P5-pr')+E5i,(-ir^3\''K")(rf-rf"; 2 = 1 Pi p^ IV. Conclusion In this paper, we study stopping sets and stopping set distributions of residue algebraic geometry codes Cn{D,G). Two descriptions of stopping sets of residue algebraic geometry codes are presented. In particular, there is a gap deg(G') — 2g + 2 ^ i ^ deg(G) + 1 where in general we do not know whether a subset with cardinality i is a stopping set or not. In the case g = 0, there is no gap and we have a complete understanding. In the case g = I, using the group structure of rational points of elliptic curves, we can characterize all the stopping sets of algebraic geometry codes from elliptic curves. Then determining the stopping sets, the stopping set distribution and the stopping distance of Cn{D,G) are reduced to deg(G')-subset sum problems in finite abelian groups. In the case g > I, only partial results can be obtained. It is still not known how to compute the stopping set distribution. For further work, there are two interesting problems: 15 (i) There are some papers contributing to compute the stopping redundancy of MDS codes [10, 12, 28]. For AG codes from elliptic curves, we have seen that the code is very closed to be MDS, i.e., MDS or near-MDS [29] (an [n, k, d] linear code is called near-MDS if d = n — k and the dual distance d-^ = k). So how about the stopping redundancy of AG codes from elliptic curves? (ii) In this paper, we have determined the stopping set distributions of AG codes from elliptic curves with the parity-check matrix H* . Can we give optimal parity-check matrices for AG codes from elliptic curves? References [1] K.A.S. Abdel-Ghaffar and J.H. Weber. Complete enumeration of stopping sets of full-rank parity- check matrices of Hamming codes. IEEE Transactions on Information Theory, 53(9):3 196-3201, Sept. 2007. [2] R. Ahlswede and H. Aydinian. On generic erasure correcting sets and related problems. IEEE Transactions on Information Theory, 58(2):501-508, 2012. [3] Q. Cheng. Hard problems of algebraic geometry codes. IEEE Transactions on Information Theory, 54:402-406, 2008. [4] T.H. Cormen, C. Stein, R.L. Rivest, and C.E. Leiserson. Introduction to Algorithms. McGraw-Hill Higher Education, 2nd edition, 2001. [5] C. Di, D. Proietti, I.E. Telatar, T.J. Richardson, and R.L. Urbanke. Finite-length analysis of low- density parity-check codes on the binary erasure channel. IEEE Transactions on Information Theory, 48(6): 1570-1579, Jun. 2002. [6] M. Esmaeili and M.J. Amoshahy. On the stopping distance of array code parity-check matrices. IEEE Transactions on Information Theory, 55(8):3488-3493, Aug. 2009. [7] M. Esmaeili, M.H. Tadayon, and T.A. Gulliver. More on the stopping and minimum distances of array codes. IEEE Transactions on Communications, 59(3):750-757, 2011. [8] T. Etzion. On the stopping redundancy of Reed-MuUer codes. IEEE Transactions on Information Theory, 52(ll):4867-4879, Nov. 2006. [9] J. Feldman, M.J. Wainwright, and D.R. Karger. Using linear programming to decode binary linear codes. IEEE Transactions on Information Theory, 51(3):954-972, Mar. 2005. [10] J. Han and RH. Siegel. On the stopping redundancy of MDS codes. In IEEE International Symposium on Information Theory, 2006, pages 2491-2495, July 2006. [11] J. Han and RH. Siegel. Improved upper bounds on stopping redundancy. IEEE Transactions on Information Theory, 53(1):90-104, Jan. 2007. [12] J. Han, RH. Siegel, and R.M. Roth. Single-exclusion number and the stopping redundancy of MDS codes. IEEE Transactions on Information Theory, 55(9):4155-4166, Sept. 2009. 16 [13] J. Han, P.H. Siegel, and A. Vardy. Improved probabilistic bounds on stopping redundancy. IEEE Transactions on Information Theory, 54(4): 1749-1753, Apr. 2008. [14] T. Hehn, O. Milenkovic, S. Laendner, and J.B. Huber. Permutation decoding and the stopping redundancy hierarchy of cyclic and extended cyclic codes. IEEE Transactions on Information Theory, 54(12):5308-5331, Dec. 2008. [15] H.D.L. HoUmann and L.M.G.M. Tolhuizen. Generic erasure correcting sets: Bounds and construc- tions. Journal of Combinatorial Theory, Series A, 113(8): 1746-1759, 2006. Special Issue in Honor of Jacobus H. van Lint. [16] H.D.L. HoUmann and L.M.G.M. Tolhuizen. On parity-check collections for iterative erasure decoding that correct all correctable erasure patterns of a given size. IEEE Transactions on Information Theory, 53(2):823-828, Feb. 2007. [17] Y. Jiang, S.-T. Xia, and F.-W. Fu. Stopping set distributions of some Reed-MuUer codes. IEEE Transactions on Information Theory, 57(9):6078-6088, Sept. 2011. [18] N. Kashyap and A. Vardy. Stopping sets in codes from designs. In Proceedings: IEEE International Symposium on Information Theory, 2003., page 122, June-4 July 2003. [19] M. Kosters. The subset sum problem for finite abelian groups. Journal of Combinatorial Theory, Series A, 120(3):527-530, 2013. [20] K.M. Krishnan and P. Shankar. Computing the stopping distance of a Tanner graph is NP-hard. IEEE Transactions on Information Theory, 53(6):2278-2280, Jun. 2007. [21] S. Laendner and O. Milenkovic. LDPC codes based on latin squares: Cycle structure, stopping set, and trapping set analysis. IEEE Transactions on Communications, 55(2):303-312, Feb. 2007. [22] J.Y. Li and D. Wan. On the subset sum problem over finite fields. Finite Fields and Their Applications, 14(4):91 1-929, 2008. [23] J.Y. Li and D. Wan. Counting subset sums of finite abelian groups. Journal of Combinatorial Theory, Series A, 119(1):170-182, 2012. [24] H. Liu, Y Li, L. Ma, and J. Chen. On the smallest absorbing sets of LDPC codes from finite planes. IEEE Transactions on Information Theory, 58(6):4014-4020, 2012. [25] A. McGregor and O. Milenkovic. On the hardness of approximating stopping and trapping sets. IEEE Transactions on Information Theory, 56(4): 1640-1650, 2010. [26] A. Orlitsky, K. Viswanathan, and J. Zhang. Stopping set distribution of LDPC code ensembles. IEEE Transactions on Information Theory, 51(3):929-953, Mar. 2005. [27] R. Schoof. Nonsingular plane cubic curves over finite fields. J. Comb. Theory, Ser A, 46(2): 183-211, 1987. [28] M. Schwartz and A. Vardy. On the stopping distance and the stopping redundancy of codes. IEEE Transactions on Information Theory, 52(3):922-932, Mar. 2006. 17 [29] M.A. ShokroUahi. On the weight distribution of elliptic codes. Research report: Institut fur Informatik. Inst, fiir Informatik, 1990. [30] J.H. Silverman. The Arithmetic of Elliptic Curves, volume 106 of Graduate Texts in Mathematics. Springer, Dordrecht, second edition, 2009. [31] H. Stichtenoth. Algebraic Function Fields and Codes, volume 254 of Graduate Texts in Mathematics. Springer- Verlag, Berlin, second edition, 2009. [32] R. Tanner. A recursive approach to low complexity codes. IEEE Transactions on Information Theory, 27(5):533-547, Sep. 1981. [33] T. Wadayama. Average stopping set weight distributions of redundant random ensembles. IEEE Transactions on Information Theory, 54(1 1):499 1-5004, Nov. 2008. [34] J.H. Weber and K.A.S. Abdel-Ghaffar. Stopping set analysis for Hamming codes. In IEEE Information Theory Workshop, 2005, pages 244-247, Aug.-l Sept. 2005. [35] S.-T. Xia and F.-W. Fu. On the stopping distance of finite geometry LDPC codes. IEEE Communications Letters, 10(5):38 1-383, May 2006. [36] S.-T. Xia and F.-W. Fu. Stopping set distributions of some linear codes. In IEEE Information Theory Workshop, 2006. ITW '06 Chengdu, pages 47-51, Oct. 2006.